#!/usr/bin/env python
# coding: utf-8

class Solution(object):
    @staticmethod
    def solution(s: str) -> str:
        # your code here
        l: int = len(s)
        # 1. 特判：空字符串
        if l == 0: return ""
        # 2. 特判：长度为1的字符串就是最长回文子串
        if l == 1: return s
        # 3. 初始化 dp table
        # dp[i][j] --> s[i:j+1]
        # j+1因为取子串操作右边是开口
        dp = [[0 for _ in range(l)] for _ in range(l)]
        # 直接记录最长回文子串信息，避免再查一边DP
        max_palindrome_len = 1; max_i = 0; max_j = 0
        # 4. 子串长为 1 的特殊处理
        i = 0
        while i < l:
            dp[i][i] = 1
            i += 1
        # 5. 子串长为 2 的特殊处理
        i = 0
        while i < l - 1:
            if s[i] == s[i + 1]:
                dp[i][i+1] = 2
                max_i = i
                max_j = i + 1
            i += 1
        # 6. 处理剩下的DP table
        len_of_substr = 3 # j = len_of_substr-1
        while len_of_substr <= l:
            i = 0
            while i < l + 1 - len_of_substr:
                if dp[i+1][i+len_of_substr-2] != 0 and s[i] == s[i+len_of_substr-1]:
                    dp[i][i+len_of_substr-1] = dp[i+1][i+len_of_substr-2] + 2
                    if dp[i][i+len_of_substr-1] > max_palindrome_len:
                        max_palindrome_len = dp[i][i+len_of_substr-1]
                        max_i = i
                        max_j = i+len_of_substr-1
                i += 1
            len_of_substr += 1
        return s[max_i:max_j+1]

    @staticmethod
    def test():
        # test code
        ts = [
            "ab",
            "a",
            "",
            "aba",
            "babad",
            "babab",
            "cabad",
            "cbbd",
        ]
        wanted = [
            "a",
            "a",
            "",
            "aba",
            "bab",
            "babab",
            "aba",
            "bb",
        ]
        for i, t in enumerate(ts):
            assert Solution.solution(t) == wanted[i], "got %r want %r" % \
            (Solution.solution(t), wanted[i])
        print("Test Done!")

if __name__ == "__main__":
    Solution.test()

